package liangtWorkSpace.suanfa;


import org.w3c.dom.Node;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 *             0
 *           1   2
 *          3 4 5 6
 */
public class TreeQZH {
    public static class Node{
        int value;
        Node left;
        Node right;

        public Node(int value) {
            this.value = value;
        }
    }


    /**
     * 先序遍历
     * @param node
     */
    public static void q(Node node){
        if (node == null){
            return;
        }
        System.out.print(node.value+" ");
        q(node.left);
        q(node.right);
    }
    /**
     * 栈实现先序
     */
    public static void qStack(Node node){
        Stack<Node> nodeStack = new Stack<>();
        Node head = node;
        if (node != null){
            nodeStack.push(head);
            while (!nodeStack.isEmpty()){
                head = nodeStack.pop();
                System.out.print(head.value+" ");
                if (head.right!= null){
                    nodeStack.push(head.right);
                }
                if (head.left != null){
                    nodeStack.push(head.left);
                }
            }
        }
    }

    /**
     * 中序遍历
     * @param node
     */
    public static void z(Node node){
        if (node == null){
            return;
        }
        z(node.left);
        System.out.print(node.value + " ");
        z(node.right);
    }
    public static void zStack(Node node){
        Node head = node;
        Stack<Node> stack = new Stack<>();

        if (head!= null){
            while (!stack.isEmpty() || head != null){
                if (head != null){
                    stack.push(head);
                    head = head.left;
                }else {
                    head = stack.pop();
                    System.out.print(head.value+" ");
                    head = head.right;
                }
            }
            System.out.println();
        }
    }

    /**
     * 后序遍历
     * @param node
     */
    public static void h(Node node){
        if (node == null){
            return;
        }
        h(node.left);
        h(node.right);
        System.out.print(node.value + " ");
    }

    /**
     * 后续
     * @param node
     */
    public static void hStack1(Node node){
        if (node == null){
            return;
        }
        Stack<Node> stack1 = new Stack<>();
        Stack<Node> stack2 = new Stack<>();

        Node head = node;
        if (head!= null){
            stack1.push(head);
            while (!stack1.isEmpty()){
                head = stack1.pop();
                System.out.print(head.value + " ");
                stack2.push(head);
                if (head.left != null){
                    stack1.push(head.left);
                }
                if (head.right != null){
                    stack1.push(head.right);
                }
            }
            System.out.println();
            while (!stack2.isEmpty()){
                System.out.print(stack2.pop().value + " ");
            }
        }
        System.out.println();
    }

    public static void hStack2(Node node){
        Node head= node; // 标记上一次弹出位置 --开始标记为头
        Node c = null; // 标记栈尾
        Stack<Node> stack = new Stack();

        if (node != null){
            stack.push(head);
            while (!stack.isEmpty()){
                c = stack.peek(); // 将c 标记为栈顶
                if (c.left != null && c.right != head && c.left != head){ // 如果上次弹出不是c的左孩子也不是c的有孩子则将左孩子压入
                    stack.push(c.left);
                }else if (c.right != null && c.right != head){ // 如果上次不是c的右孩子则将有孩子压入
                    stack.push(c.right);
                }else { // 如果h是c的左孩子或者有孩子则将c弹出并打印
                    System.out.print(stack.pop().value + " ");
                    head = c;
                }
            }
            System.out.println();
        }

    }

    /**
     * 按层输出树
     * @param node
     */
    public static void duilie(Node node){
        if (node == null){
            return;
        }
        Queue<Node> queue = new LinkedList<>();

        Node head = node;
        queue.add(head);
        while (!queue.isEmpty()){
            Node n = queue.poll();
            System.out.print(n.value + " ");
            if (n.left != null){
                queue.add(n.left);
            }
            if (n.right != null){
                queue.add(n.right);
            }
        }
        System.out.println();
    }

    /**
     * 求层的最宽
     */
    public static  int maxLevel(Node node){
        int max = 0;
        HashMap<Node,Integer> map = new HashMap();
        Queue<Node> queue = new LinkedList();
        int curLevel = 1; // 当前层级
        int countLevel = 0;
        int count = 0;
        map.put(node,countLevel);
        queue.add(node);
        while (!queue.isEmpty()){
            //获取当前节点
            Node cur = queue.poll();
            //如果当前节点的左节点存在 则将左节点添加到队列
            System.out.print(cur.value + " ");
            curLevel = map.get(cur);
            if (cur.left != null){
                map.put(cur.left,curLevel+1);
                queue.add(cur.left);
            }
            // 如果当前节点的右节点存在，则将右节点添加到队列中
            if (cur.right != null){
                map.put(cur.right , curLevel + 1);
                queue.add(cur.right);
            }

            // 如果当前节点等于统计节点则 统计数 + 1
            if (curLevel == countLevel){
                count ++;
            }else {
                // 如果当前节点层级不等于统计节点层级，
                // 则将统计节点曾杰修改为当前节点层级
                // 计算当前节点宽度是否为最宽，并将统计次数初始化为 1
                max = Math.max(count,max);
                countLevel = curLevel;
                count = 1;
            }

         }
        System.out.println();
        max = Math.max(max,count);
        System.out.println("最宽层节点个数="+max);
        return max;
    }

    /**
     * 计算最大宽度
     */
    public static int maxLevel2(Node node){
        int max = 0;

        Node curEnd = node; // 标记层级结束节点
        Node cur = null; // 当前节点
        Node nextCur = null;
        Queue<Node> queue = new LinkedList<>();// 将树存放到队列中，可以划分层级
        queue.add(node);
        int count = 0;
        while (!queue.isEmpty()){
            cur = queue.poll();
            System.out.print(cur.value + " ");
            if (cur.left != null){
                queue.add(cur.left);
                nextCur = cur.left;
            }
            if (cur.right != null){
                queue.add(cur.right);
                nextCur = cur.right;
            }
            count++;
            if (cur == curEnd){
                max = Math.max(count,max);
                count = 0;
                curEnd = nextCur;
            }
        }
        System.out.println();
        System.out.println("最大节点数："+max);
        return max;
    }

    /**
     * 序列化
     */
    public static void x(Node node,Queue ans){
        if (node == null){
            ans.add(null);
            return;
        }
        ans.add(node);
        x(node.left,ans);
        x(node.right,ans);
    }

    /**
     * 反序列化
     * @param ans
     */
    public static Node x(Queue<Node> ans){
        if (ans.peek() == null){
            ans.poll();
            return null;
        }
        Node head = ans.poll();
        head.left = x(ans);
        head.right = x(ans);
        return head;
    }

    /**
     * 获取树
     * @return
     */
    public static Node getTree(int time){
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);

        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        return node1;
    }

    public static void main(String[] args) {
        Node node = getTree(7);
        System.out.println("------- 前序遍历 -----");
        System.out.println("预期结果：1 2 4 5 3 6 7 ");
        q(node);
        System.out.println();
        qStack(node);
        System.out.println();
        System.out.println("-----------中序遍历------------");
        System.out.println("中序遍历：预期结果4 2 5 1 6 3 7");
        zStack(node);
        z(node);
        System.out.println("-----------后序遍历------------");
        System.out.println("后续预期输出：4 5 2 6 7 3 1");
        h(node);
        System.out.println();
        hStack1(node);
        hStack2(node);
        System.out.println("------- 按层输出树 -----------------");
        System.out.println("预期输出结果：1 2 3 4 5 6 7 ");
        duilie(node);
        maxLevel(node);
        maxLevel2(node);
        //序列化
        System.out.println("--------- 序列化 ---------------");
        Queue<Node> queue = new LinkedList<>();
        x(node,queue);
//        while (!queue.isEmpty()){
//            Node cur = queue.poll();
//            if (cur != null){
//                System.out.print(cur.value +" ");
//            }else {
//                System.out.print("n ");
//            }
//        }
        System.out.println();
        System.out.println("反序列化");
        Node cur = x(queue);
        q(cur);
        System.out.println("8|4 = "+(8|4));
        System.out.println("8^4 = "+(8^4));
        System.out.println("8&4 = "+(8&4));
        System.out.println((28-4) == (28&(~4)));
    }

}
